#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 113. 路径总和 II.py
@time: 2022/1/19 23:58
@desc: https://leetcode-cn.com/problems/path-sum-ii/
>　给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

1. Ot(N2), Os(N)
'''
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: List[List[int]]
        """
        def dfs(root, targetSum):
            if not root: return
            path.append(root.val)
            targetSum -= root.val
            if 0==targetSum and not root.left and not root.right:
                # 这里找到后不应立刻return，而应该继续执行并执行弹出当前节点与其父节点（因为就算兄弟节点也满足，也是相同的解）
                res.append(list(path))
            dfs(root.left, targetSum)
            dfs(root.right, targetSum)
            path.pop()

        path = []
        res = []
        dfs(root, targetSum)
        return res

if __name__ == '__main__':
    root = TreeNode(5,
                    left=TreeNode(4, left=TreeNode(11, left=TreeNode(7), right=TreeNode(2))),
                    right=TreeNode(8, left=TreeNode(13), right=TreeNode(4, left=TreeNode(5), right=TreeNode(1))))
    res = Solution().pathSum(root, 22)
    print(res)